package swordoffer.offer40;

import java.util.ArrayList;
import java.util.PriorityQueue;

public class HeapSolution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        int len = input.length;
        if(k == 0 || k > len){
            return res;
        }
        buildMaxHeap(input, k);
        for(int i = k; i < len; i++){
            if(input[i] < input[0]){
                swap(input, 0, i);
                downAdjust(input, 0, k);
            }
        }
        for(int i = 0; i < k; i++){
            res.add(input[i]);
        }
        return res;
    }
    /*
        构建最大堆
     */
    public void buildMaxHeap(int[] nums, int k ){
        for(int i = k / 2 - 1; i >= 0; i--){
            downAdjust(nums, i, k);
        }
    }
    /*
        下沉操作
     */
    public void downAdjust(int[] nums, int p, int k){
        int c = p * 2 + 1;
        while(c < k){
            if(c + 1 < k && nums[c + 1] > nums[c]){
                c++;
            }
            if(nums[p] > nums[c]){
                break;
            }
            swap(nums, p, c);
            p = c;
            c = p * 2 + 1;
        }
    }
    public void swap(int[] nums, int i , int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
